Date: Tue, 14 Jan 1997 22:41:16 GMT
Server: NCSA/1.5.2
Last-modified: Tue, 06 Feb 1996 20:38:57 GMT
Content-type: text/html
Content-length: 7072

<html>
<head>
<title>198:206 - DISCRETE STRUCTURES II</title>
</head>
<body>
<center>

<h1>198-206: DISCRETE STRUCTURES II</h1>
<h3>Spring 1996</h3>
<h2>Course Syllabus</h2>
<b>INSTRUCTOR:   Prof. Chitoor V. Srinivasan</b>,<br>  Office:
CoRE 324, Phone 908-445-2019, <br>Email: srinivas@cs.rutgers.edu.<p>
</center>

<b>TEXTS:</b><br>

<ul>
<li><b>Kenneth H. Rosen</b>, <i>Discrete Mathematics and its
Applications,</i> for the lectures on counting.  This is the same text
that was used in Cs205.

<li><b>Sheldon Ross</b>  <i>A First Course in
Probability</i>, MacMillan, 1994.

<li>Notes to be bought from Copy Center in Busch Campus Student Center.
</ul>
<p>

<b>Lectures:</b><br>
<ul>
<li><b>Lecture 1:</b> (Jan 16)   Thought Experiments, Sample
Spaces, Events, Probabilities and Counting.  When is a counting
correct?  Sum and Product Rules.<br>

<i>Readings</i>: Relevant sections from Lecture notes, Chapter 4 Rosen
and Chapter 1 of Sheldon Ross<p>


<li><b>Lecture 2:</b>  (Jan 18) Subtraction and Division Rules
(counting equivalence classes), Permutations, Combinations.<br>

<i>Readings</i>: Relevant sections from Lecture notes, Chapter 4 of Rosen
Chapter 1 of Sheldon Ross.<p>

<li><b>Lecture 3:</b>   (Jan 23) Permutations and Combinations,
Selections with and without repetition, Pascal's Triangle.<br>

<i>Readings</i>: Relevant sections from Lecture notes, Chapter 4 of Rosen
Chapter 1 of Sheldon Ross.<p>

<li><b>Lecture 4:</b>  (Jan 25)  Pigeon-Hole Principle.<br>

<i>Readings</i>: Relevant sections from Lecture notes, Chapter 4 of Rosen
Chapter 1 of Sheldon Ross.<br><b>Start working on Review Problems I.</b><p>

<li><b>Lecture 5:</b>  (Jan 30) Inclusion/Exclusion and
Derangements.<br>

<i>Readings</i>: Relevant sections from Lecture notes, Rosen's book and
Chapter 1 of Sheldon Ross.<br> <b>Continue working on Review Problems I.</b><p>

<li><b>Lecture 6:</b> (Feb 1) Discussion of Review Problems I. 
Solutions will be distributed in Class.<br>

<i>Readings</i>: Complete your work on Review Problems I.  You must
have questions to ask me during the review in class.<p>


<li><b>Lecture 7:</b>   (Feb 6) Generating Functions I.  <br>

<i>Readings</i>: Relevant sections from Lecture notes, Rosen's book and
Chapter 1 of Sheldon Ross.  See Appendix 3 in Rosen's book. <br>
<b>Start working on Review Problems II.</b><p>

<li><b>Lecture 8:</b> (Feb 8) Generating Functions  II.  Work
on review problems I and II. <br>

<i>Readings</i>: Class Notes and Appendix 3 in Rosen's Book.  Continue
work on Review Problems I and II.<p>
 <i> Supplemental Readings in the
order increasing sophistication</i>:

<ul>
<li>Berman & Fryer, <i>Introduction to Combinatorics</i>, Academic
Press, 1972.  Chaper 6.  Gives a simple introduction with interesting
examples and problems.  Easy reading.

<li>C.L. Liu, <i>Introduction to Combinatorial Mathematics</i>,
Computer Science Series, McGraw Hill, 1968.  Chaper 2.  Has some
very tough problems.

<li>William Feller, <i>An Introduction to Probability Theory and
its Applications</i>, Volume I (2nd Edition), John Wiley, 1958. Chapter
X1.  Discusses the subject thoroughly with advanced topics.
</ul>
<p>

<li><b>Lecture 9:</b>  (Feb 13) Recurrence Relations I:  Using 
recurrence relations to state problems.  Solutions of recurrence
relations.<br>

<i>Readings</i>: Class notes, Rosen Chapters 5.1 through 5.3 and
Appendix 3.  Continue work on review problems II.<p>

<li><b>Lecture 10:</b> (Feb 15) Recurrence Relations II: Closed
form solutions for Homogeneous Recurrence Relations.<br>

<i>Readings</i>:  Rosen Chapters 5.1 through 5.3  and Class Notes.
Continue work on review problems II. <p>

<li><b>Lecture 11:</b> (Feb 20) Recurrence Relations III:  Using
Generating Functions to solve recurrence relations.

<i>Readings</i>: Class notes and Appendix 3 in Rosen's book.  Work on
review problems II.<p>

<li><b>Lecture 12:</b>  (Feb 22) Discussion of Review Problems I
and II,  Homework Problems and Previous Exam problems.<p>

<li><b>MID-TERM EXAMINATION: (Feb 27) Tuesday, 6:10 - 7:30 pm</b>.<p>

<li><b>Lecture 13:</b> (Feb 29) <i>Discrete Probability,
Introduction</i>: Events, Axioms of Probability, Conditional Probability.

<i>Readings</i>:  Chapter 2 of Sheldon Ross. Start work on Review problems III.<p>

<li><b>Lecture 14:</b> (Mar 5) <i>Conditional Probability
I</i>: Joint and Conditional probabilities, total probability theorem
and Bayes' theorem.<br>

<i>Readings</i>: Chapter 3 of Sheldon Ross.  Continue work on Review
problems II and III.<p>

<li><b>Lecture 15:</b> (Mar 7) <i>Conditional Probability
II</i>: More on Total Probability and Bayes' theorems, and
Independence.<br>

<i>Readings</i>: Chapter 3 of Sheldon Ross. Continue work on Review
problems II and III.<p>

<li><b>Spring Recess</b>:  Have a Happy Vacation!<p>

<li><b>Lecture 16:</b>  (Mar 19) <i>Bernoulli Trials and
Distributions\/</i>: <br>

<i>Readings</i>: Chapter 4 of Sheldon Ross. Continue work on Review
problems II and III.<p>

<li><b>Lecture 17:</b> (Mar 21) <i>Bernoulli Trials and
Distributions\/</i>: <br>

<i>Readings</i>: Chapter 4 of Sheldon Ross.  Continue work on Review
problems II and III.  Start work on Review problems IV.<p>

<li><b>Lecture 18:</b> (Mar 26) <i>Random Variables,
Expectation, Variance and Standard Deviation</i>:<br>

<i>Readings</i>: Chapter 4 of Sheldon Ross.  Continue work on Review
problems III and IV.<p>

<li><b>Lecture 19:</b> (Mar 28) <i>Random Variables,
Expectation, Variance and Standard Deviation</i>:<br>

<i>Readings</i>: Chapter 4 of Sheldon Ross.  Continue work on Review
problems III and IV.<p>

<li><b>Lecture 20:</b>  (Apr 2) <i>Distributions, Their
expectations and Variance</i>.<br>

<i>Readings</i>: Chapter 4 of Sheldon Ross.  Continue work on Review
problems III and IV.<p>

<li><b>Lecture 21:</b> (Apr 4) <i>Languages and Grammars and
Finite State Machines</i>:<br>

<i>Readings</i>:  Chapter 10.1 and 10.2 of book by 
Rosen.<p>

<li><b>Lecture 22:</b> (Apr 9)  <i>Finite State Machines and
Language Recognition</i>:<br>

<i>Readings</i>: Chapter 10 of Rosen.  Continue work on Review problems
III and IV.<p>

<li><b>Lecture 23:</b>  (Apr 11) <i>Finite State Machines and
Language Recognition</i>:<br>

<i>Readings</i>: Chapter 10 of Rosen.  Continue work on Review problems
I, II, III and IV.<p>

<li><b>Lecture 24:</b>  (Apr 16) <i>Graphs</i>.<br>

<i>Readings</i>: Chapter 7 of Rosen.  Continue work on Review problems
I, II, III and IV. <p>

<li><b>Lecture 25:</b>  (Apr 18) <i>Graphs</i>.<br>

<i>Readings</i>: Chapter 7 of Rosen.  Continue work on Review problems I, II,
III and IV.<p>

<li><b>Lecture 26:</b>  (Apr 23) <i>Graphs</i>.<br>

<i>Readings</i>: Chapter 7 of book by Rosen.  Continue work on Review problems
I, II, III and IV. <p>

<li><b>Lecture 27:</b>  (Apr 25) <i>Review</i>.<br>

<i>Readings</i>: Do all review problems and look through all past
mid-term and final examination questions.  <p>

<li><b>Lecture 28:</b>  (Apr 30) <i>Review</i>.<p>

<li><b>FINAL EXAMINATION: Thursday, May 2nd,   8 to 11 pm</b>.
</ul>

</body>
</html>


